import java.lang.module.ModuleReader;
import java.util.Arrays;
import java.util.Scanner;

public class demo {

    //    字符串中找出连续最长的数字串
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String ret = "";
        String cur = "";
        int i = 0;///此处不在下一行的for循环中进行定义是因为需要记下i的值,用于比较最后位于末尾的数字串
        for (; i < str.length(); i++) {
            char ch = str.charAt(i);
//            在对字符串进行遍历时.当ch为数字时, 自动拼接为字符串
            if (ch>='0' && ch<='9') {
                cur = cur + ch + "";
            }else {//当ch不为数字时, 比较字符串长度,重新对ret字符串赋值 并将cur置空
                // 理解  NULL是不指向任何对象, 而 "" 表示:指向对象为空
                if (ret.length() < cur.length()) {
                    ret = cur;//ret指向cur指向的对象
                }
                cur = "";
            }
        }
//        判断特殊情况 例如：123asd123456
        if (i == str.length() && ret.length()<cur.length()){
            ret = cur;
        }
        System.out.println(ret);
    }




    //数组中出现次数超过一半的数字
//思路一：
//众数：就是出现次数超过数组长度一半的那个数字
//如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，
//最后留下的数肯定是众数。

    public static int MoreThanHalfNum_Solution(int[] arr) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空");
            return -1;
        }
        int ret = arr[0];//先保存数组第一个元素  从这个开始比较
        int count = 1;// 两个数进行比较 如果不同就-- 相同就++
        for (int i = 1; i < arr.length; i++) {
            if (ret == arr[i]) {
                count++;
            }else {
                count--;
            }
            if (count == 0) {
                ret = arr[i+1];
                count = 1;
            }
        }
//        判断ret是否符合条件，即出现次数大于数组长度的一半
        count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (ret == arr[i]) {
                count++;
            }
        }
        return count>arr.length/2? ret : 0 ;
    }

//    思路二：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。这种方法虽然容易理解，但由于
//涉及到快排sort，其时间复杂度为O(NlogN)并非最优；

    public static int MoreThanHalfNum_Solution2(int[] arr) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空");
            return -1;
        }
        Arrays.sort(arr);
        int ret = arr[arr.length/2];
//        判断ret是否符合条件，即出现次数大于数组长度的一半
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (ret == arr[i]) {
                count++;
            }
        }
        return count>arr.length/2? ret : 0 ;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {1,2,3,2,2,2,5,4,2};
        int sum = MoreThanHalfNum_Solution(arr);
        System.out.println(sum);
    }


}









